package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-01-10 14:53
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 9, 3, 0, 8, 2, 7, 6, 5, 9, 6, 8, 4};
        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序
     * 1.去第一个数为标椎
     * 2.从最后进行比较，将小于标注的数一道左侧
     * 3.从最左侧进行比较，将大于标准的数移到右侧
     *
     * @param arr   // 要比较的数组
     * @param start // 开始位置
     * @param end   // 结束位置
     */
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int standard = arr[start];
        int low = start;
        int high = end;
        while (low < high) {
            // 先比较右侧的数字，如果右侧的数字大于stard,则high--
            while (low < high && standard <= arr[high]) {
                high--;
            }
            // 右侧的数字小于左侧的数字，进行交换
            arr[low] = arr[high];
            // 比较左侧的数字和stard的大小，下雨stard则low++
            while (low < high && arr[low] <= standard) {
                low++;
            }
            arr[high] = arr[low];
        }
        // 将sard放入到low处
        arr[low] = standard;

        // 递归比较左侧的数字
        quickSort(arr, start, low);
        // 递归比较右侧的数字
        quickSort(arr, low + 1, end);
    }
}
